package cn.bellychang.leetcode.question033;

/**
 * @author ChangLiang
 * @date 2021/3/12
 */
public class Solution2 {

    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = ((right - left)>>1) + left;
            if (nums[mid] == target) {
                return mid;
            }
            // nums[mid]小于最右边值 说明右边是有序的
            if (nums[mid] < nums[right]) {
                // 在有序的半段里用首尾来判断目标值是否在这一区段内

                // 左侧值小于target并且右侧值大于等于target 说明在这个区域内
                if (nums[mid] < target && nums[right] >= target) {
                    // 缩小范围
                    left = mid + 1;
                } else {
                    // 不在这个区域内 缩小范围
                    right = mid - 1;
                }
            } else {
                // nums[mid]大于最右边值 说明左边是有序的

                // 左侧值小于等于target 并且 右侧值大于等于target 说明在这个区域内
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    // 不在这个区域内 缩小范围
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
